package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/24 9:10
 * @description <p>字符串中的所有变位词 </p>
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 题目：输入字符串 s1 和 s2，如何找出字符串 s2 的所有变位词在字符
 * 串 s1 中的起始下标？假设两个字符串中只包含英文小写字母。例如，字符
 * 串 s1 为"cbadabacg"，字符串 s2 为"abc"，字符串 s2 的两个变位词"cba"和"bac"
 * 是字符串 s1 中的子字符串，输出它们在字符串 s1 中的起始下标 0 和 5。
 */
public class toOffer3_2_15 {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> list = findAnagrams(s, p);
        for (Integer element : list) {
            System.out.print(element + " ");
        }

    }

    /**
     * 思想与3_2_14类似，主要区别就是新建个list集合装下标就行
     * @param l
     * @param s
     * @return
     */
    public static List<Integer> findAnagrams(String l, String s) {

        ArrayList<Integer> list = new ArrayList<>();

        //在l里找s，s的长度应当比l小
        if (s.length() > l.length()) {
            return list;
        }

        Map<Character, Integer> map = new HashMap<>(26);
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            map.put(l.charAt(i), map.getOrDefault(l.charAt(i), 0) - 1);
        }

        if (judge(map)) {
            list.add(0);
        }

        for (int i = s.length(); i < l.length(); i++) {
            char slow = l.charAt(i - s.length());
            char fast = l.charAt(i);

            map.put(slow, map.getOrDefault(slow, 0) + 1);
            map.put(fast, map.getOrDefault(fast, 0) - 1);
            if (judge(map)) {
                list.add(i - s.length() + 1);
            }
        }

        return list;
    }

    /**
     * 判断map里的v是否全为0
     *
     * @param newMap
     * @return
     */
    public static boolean judge(Map<Character, Integer> newMap) {
        for (Character key : newMap.keySet()) {
            if (newMap.get(key) != 0) {
                return false;
            }
        }
        return true;
    }
}
